package com.zwy.Algorithm;

import java.util.LinkedList;
import java.util.List;

/*
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，
就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，
按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，
就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点
称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
 */
//使用回溯法解决全排列问题
//给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
public class backtracking {
    public static void main(String[] args) {
        Solution solution = new backtracking().new Solution();
        int []arr={1,2,3};
        solution.permute(arr);


    }
    class Solution {
        List<List<Integer>>res=new LinkedList<>();
        public List<List<Integer>> permute(int[] nums) {
            LinkedList list=new LinkedList();
            backtrack(nums,list);
            return res;
        }
        public void backtrack(int []nums,LinkedList<Integer>list){
            if(list.size()==nums.length){
                res.add(new LinkedList<>(list));
                return;
            }
            for (int i = 0; i <nums.length ; i++) {
                if(list.contains(nums[i]))continue;
                list.add(nums[i]);
                backtrack(nums,list);
                list.removeLast();
            }
        }
    }
}
